/*
 * @lc app=leetcode.cn id=399 lang=java
 *
 * [399] 除法求值
 */

// @lc code=start
class Solution {
    //这个BST的方法我没看懂后面那一段
    public double[] calcEquation1(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int nvars = 0;//代表不同的字符串的个数，即不同的点的个数。
        Map<String, Integer> variables = new HashMap<String, Integer>();

        int n = equations.size();
        for (int i = 0; i < n; i++) {
            if (!variables.containsKey(equations.get(i).get(0))) {
                variables.put(equations.get(i).get(0), nvars++);
            }
            if (!variables.containsKey(equations.get(i).get(1))) {
                variables.put(equations.get(i).get(1), nvars++);
            }
        }
        // 找出equations中所有不同的字符串，并通过哈希表将每个不同的字符串映射成不同的整数。


        // 对于每个点，存储其直接连接到的所有点及对应的权值
        List<Pair>[] edges = new List[nvars];//为何不用List<List<pair>> edges = new Arraylist();这种。
        for (int i = 0; i < nvars; i++) {
            edges[i] = new ArrayList<Pair>();
        }
        for (int i = 0; i < n; i++) {
            int va = variables.get(equations.get(i).get(0)), vb = variables.get(equations.get(i).get(1));
            edges[va].add(new Pair(vb, values[i]));
            edges[vb].add(new Pair(va, 1.0 / values[i]));
            //edges索引是a，value中放了对应的b和相应的a/b的值。
        }

        int queriesCount = queries.size();
        double[] ret = new double[queriesCount];
        for (int i = 0; i < queriesCount; i++) {
            List<String> query = queries.get(i);//拿到一个式子。
            double result = -1.0;//默认是-1
            if (variables.containsKey(query.get(0)) && variables.containsKey(query.get(1))) {//如果存在这两个变量
                int ia = variables.get(query.get(0)), ib = variables.get(query.get(1));//先拿到字符串
                if (ia == ib) {
                    result = 1.0;//两者相等的情况
                } else {
                    Queue<Integer> points = new LinkedList<Integer>();
                    points.offer(ia);//队列中插入被除数
                    double[] ratios = new double[nvars];
                    Arrays.fill(ratios, -1.0);
                    ratios[ia] = 1.0;

//通过广度优先搜索的方式，不断更新起点与当前点之间的路径长度，直到搜索到终点为止。
                    while (!points.isEmpty() && ratios[ib] < 0) {//这一部分有点不懂，应该是BST的内容，但是
                        int x = points.poll();
                        for (Pair pair : edges[x]) {
                            int y = pair.index;
                            double val = pair.value;
                            if (ratios[y] < 0) {
                                ratios[y] = ratios[x] * val;
                                points.offer(y);
                            }
                        }
                    }
                    result = ratios[ib];
                }
            }
            ret[i] = result;
        }
        return ret;
    }

    // floyes方法比较好懂。
    // 规则是如果a/b = x, b/c = y， 那么a/c = (a/b) * (b/c) = xy。所以g[i][j] = g[i][k] * g[k][j]即可。
    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        int nvars = 0;
        Map<String, Integer> variables = new HashMap<String, Integer>();

        int n = equations.size();
        for (int i = 0; i < n; i++) {
            if (!variables.containsKey(equations.get(i).get(0))) {
                variables.put(equations.get(i).get(0), nvars++);
            }
            if (!variables.containsKey(equations.get(i).get(1))) {
                variables.put(equations.get(i).get(1), nvars++);
            }
        }
        //同样的处理，拿到不重复的String的数量，以及各自对应的下标。

        double[][] graph = new double[nvars][nvars];//这就是floyed矩阵
        for (int i = 0; i < nvars; i++) {//初始化默认值
            Arrays.fill(graph[i], -1.0);//先默认全放-1
        }
        for (int i = 0; i < n; i++) {//首次更新。
            int va = variables.get(equations.get(i).get(0)), vb = variables.get(equations.get(i).get(1));
            graph[va][vb] = values[i];//代表a/b
            graph[vb][va] = 1.0 / values[i];//代表b/a
        }

        for (int k = 0; k < nvars; k++) {//后续更新过程
            for (int i = 0; i < nvars; i++) {
                for (int j = 0; j < nvars; j++) {
                    if (graph[i][k] > 0 && graph[k][j] > 0) {
                        graph[i][j] = graph[i][k] * graph[k][j];//更新规则
                    }
                }
            }
        }

        int queriesCount = queries.size();
        double[] ret = new double[queriesCount];
        for (int i = 0; i < queriesCount; i++) {
            List<String> query = queries.get(i);
            double result = -1.0;
            if (variables.containsKey(query.get(0)) && variables.containsKey(query.get(1))) {
                int ia = variables.get(query.get(0)), ib = variables.get(query.get(1));
                if (graph[ia][ib] > 0) {
                    result = graph[ia][ib];
                }
            }
            ret[i] = result;
        }
        return ret;
    }
}

class Pair {
    int index;
    double value;

    Pair(int index, double value) {
        this.index = index;
        this.value = value;
    }

}

// @lc code=end

